perm filename SEARCH[W76,JMC]3 blob sn#876727 filedate 1989-09-05 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00031 00003	.bb "Search of Cartesian product spaces."
C00033 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
[replaced by search.tex[w76,jmc]]
.FONT 9 "MISC25";
.AT "¬" ⊂"%9-%*"⊃;
.EVERY HEADING(Finitary Search,%3Draft%1,{DATE})
.cb FINITE STATE SEARCH PROBLEMS
.SKIP 3
.cb "John McCarthy, Stanford University"
.SKIP 2



.ITEM←0;
.bb "#. Introduction"

	We have found a class of search problems that may admit very
efficient algorithms and to which many search problems that arise
naturally can be reduced.  The reduction itself
will often be a more difficult heuristic problem than the subsequent
solution, but nevertheless this way of dividing problems may often
be the best way of conquering them.

	The methods to be described are applicable  to what I want to
call %2non-mental quasi-static problems%1.  "Quasi-static" means that
each action of the problem solver gives rise to a new state,  and the
problem is  to find  a sequence  of actions  leading from  an initial
state to  a state having desired properties.  "Non-mental" means that
the problem is to be solved with the information provided; strategies
to  acquire additional information  from the  external world  are not
required, although conclusions may have to be deduced.  Almost all of
the  problems  solved  using STRIPS  and  PLANNER  and  CONNIVER  are
quasi-static, and most of them are non-mental.

	%2Finite state search problems%1 have %2Boolean search problems%1
as an important subclass.  These are formulated as follows:

	The state of the system is characterized by the values of
Boolean variables %2p%41%1,...,%2p%4n%1.  An allowed transformation of
state is represented by a formula such as

	%2p%41%2∧¬p%42%2∧¬p%43%2∧p%44%1 => %2p%43%2∧¬p%44%2∧p%46%1.

The meaning of the formula is that if a state satisfies the
premiss of the transformation, then the transformation takes it
into a state satisfying the conclusion, where unmentioned %2p%1's
are left unchanged.

	The desired state is characterized by a similar formula.

	There is a straightforward breadth first search algorithm
for a sequence of transformations leading to the desired final
state.  It represents a state by a Boolean vector, e.g. by the bits
in a machine word.  The transformation is represented by four
Boolean words, a mask each for the left and right parts and
vectors whose ones correspond to the unnegated propositional variables
in the left and right parts.
If the state is denoted by ⊗s, the masks
by %2m%4L%1 and %2m%4R%1 respectively, and the left and right
parts by ⊗L and ⊗R respectively, then the condition for applicability
of the transformation is

	%2m%4L%1 ∧ ⊗s = ⊗L 
.skip 1
and the state resulting from the transformation is

	(%2m%4R%1 ∧ ⊗s ) ∨ ⊗R ,
.skip 1

assuming the logical operators are given a bitwise interpretation.

Therefore, a transformation can be applied to a state in
a few machine instructions, and it seems that problems involving
up to say twenty Boolean variables can be done in a few seconds
by a program whose basic loop computes the successors of the
newly found states and sorts the newly found states against the
set of all states found so far in order to discard old states.
(If previously found states are not discarded, then the
algorithm will blow up on rather small problems).
The algorithm will usually run out of main memory before it
runs out of time, so it may be worthwhile to work out variants of
the algorithm that use secondary storage.

	In the general form of the finite state search problem, the
state is characterized by the values of a number of variables each
taking values in small finite sets.  For example, there might be
variables %2x%41%1,...,%2x%45%1, where %2x%41%1 takes the values
0,...,4, and %2x%42%1 takes values 0,...,7, etc.  The premiss
of a transformation is a conjunction such as

	%2x%41%1=3∧%2x%42%1≠1∧%2x%44%1=3,

.SKIP 1
and the conclusion is a collection of assignments such as

	%2x%41%1←2;%2x%43%1←4;%2x%45%1←0.

The transformations are interpreted just as in the Boolean case, i.e.
if a state satisfies the premiss of the transformation, it can
be transformed by making the assignment specified in its conclusion.

	There is also a fast ⊗standard ⊗algorithm for the general
case of finite state search.  It packs the values of the
state variables into a machine word leaving an unused ⊗guard ⊗bit between
the strings of bits representing the components.  The premiss of a
transformation is tested in parallel in the following way:
First we ⊗and the state with a mask that has all %3one%1's in the fields
coresponding to the variables subjected to conditions.
We then ⊗exclusive ⊗or with the word representing the right hand sides
of the conditions of the premiss,
so that the new word has %3zero%1's in precisely those
fields where the components of the state equal the right hand
sides of the conditions.  Next we ⊗add a word with
all %3one%1's in those fields, getting a carry into the guard bits
where the equalities are not satisfied.  Now we mask out all but the
guard bits and test for equality with a word that has %3one%1's in
precisely those guard bits where inequality was wanted.
If the condition is satisfied, making the transformation is just
a matter of masking out the fields to which assignments are made
and %2or%1ing in the right hand sides of the assignments.


.bb "#. Examples"

	1. Suppose there are four blocks called ⊗A, ⊗B, ⊗C, and ⊗D on
a table, and that a state is characterized by the set of relations
of the form ⊗on(x,y) that are satisfied.  Since there are four blocks
each of which can be on any of the other blocks or the table, the
state is determined by the values of 16 Boolean variables.  If we
have %2p%41%2 = on(A,B), %2p%42%2 = on(A,C), p%43%2 = on(A,D),
p%44%2 = on(A,Table), p%45%2 = on(B,A)%1, etc. in the obvious way,
then the allowed transformations are

	
	¬%2p%45%1∧¬%2p%49%1∧¬%2p%413%1∧¬%2p%410%1∧¬%2p%414%1 => {
%2p%41%1∧¬%2p%42%1∧¬%2p%43%1∧¬%2p%44%1, etc. -

one transformation giving the conditions for putting each block on each
other or the table.  While there are 2%516%1 = 65536 states, only
4%54%1 = 256 of them are legitimate since a block is in exactly one
place in any given state.  Therefore, the search for a path to a goal
will be quite fast.

	The same problem can be represented as a finite state search
problem by introducing the variables %2x%41%1,...,%2x%44%1 each taking
the values 0 through 4 and giving the block or table that supports each
block and therefore 5%54%1 = 625 states.  If we use a different space
for the support of each block, then we are down to the minimum 256
states.  Naturally, if a human is setting up the problem, this is
the right thing to do, but if a program is generating the finite state
search problem from the problem expressed in a different formalism,
we may still get a good result even if it misses the fact that a block
cannot be on top of itself.

	Again there are sixteen transformations, and the one corresponding
to the above Boolean transformation is

	%2x%42%1≠1 ∧ %2x%43%1l≠1 ∧ %2x%44%1≠1 ∧ %2x%43%1≠2 ∧ %2x%44%1≠2 => {
%2x%41%1 ← 2.

	Unfortunately, the standard algorithm for finite state search
won't work for the block moving problem, because the variable %2x%43%1,
for example, must satisfy two inequality conditions in the first transformation.
This can be fixed by representing each variable twice, and everything
will still fit in a machine word.

	2. The second example is the %2Tower of Hanoi%1 problem.
There is a variable for each disk taking value 1, 2, or 3 stating
what spike it is on.  A twelve disk state is representable in a 36 bit
word, and there are 3%512%1 = 531441 states to be searched so the
problem is quite feasible by this brute force method.


.bb "#. Improved Algorithms"

	The standard algorithms for Boolean or finite state search may
be the best algorithm in general although I doubt it.
However, it would seem that most problems arising in AI will have
structures that permit heuristics that greatly reduce the search.

	The finite state search algorithm can be improved by
generalizing the conditions that can serve as premisses.  There
is no point in introducing disjunctions as well as conjunctions into
the premiss because this is handled by having a collection of rules -
one for each disjunct.  However, we can allow ranges of values for
the variables.  It is necessary only to choose suitable constants
represent the value of each variable twice by the contents of field
in the word and choose suitable constants to be added to the fields.
Then the values of the guard bits tell whether the addition produced
overflow and after masking out all but certain guard bits, the program
can test for equality with a suitable constant.  I don't yet have
examples where this pays off.

	A second possible improvement involves arranging the transformations
into a tree of conditions, so that certain transformations are
tested only if suitable conditions are satisfied.

	The above improvements don't change the search space; they
merely reduce the number of transformations.  However, the
%2Tower of Hanoi%1 problem is reduced by a heuristic that seems to
have wide applicability.  Namely the bottom disk has to be moved,
and the condition for moving it is that none of the other disks
be on it or on its destination spike.  Therefore, the problem splits
into three parts - moving the other disks, moving the bottom disk,
and moving the others again.  Suppose that a heuristic is used that
can recognize this.  Then it will also recognize that each of the
moves of ⊗n-1 disks has the same character.  Thus there won't be
any blind search of a space of 3%5n%1 points, but rather a direct
problem reduction that will eventually involve 2%5n%1-1 trivial moves.
This heuristic does not explicitly recognize the symmetries of the
problem that permit us to see in a small amount of reasoning that
the %2Tower of Hanoi%1 is solvable for any ⊗n. 

	There is another heuristic that also solves the %2Tower of
Hanoi%1 problem.  Namely the conditions for moving the top disk
are null and it can be moved to any spike.  Therefore, its variable
can be given an arbitrary value without changing the values of the
other variables.  This means that when the position of the top disk
occurs in the condition for moving another disk, this part of the
condition can always be satisfied, and therefore we can get a %2reduced
set of transformations%1 by eliminating the conditions on the top disk
from the conjunctions.  However, in this reduced set, the second
disk will enjoy the property of the top disk in the previous set of
transformations.  Successive application of this heuristic will
wipe out the entire problem.

	Let's call these heuristics the %2bottom-up%1 and ⊗top-down 
heuristics respectively.  In the %2Tower of Hanoi%1 case, either
trivializes the problem, and one might suspect they are equivalent.
In general, it would seem that they are not equivalent but rather
dual and correspond to problem reductions much used in human problem
solving.  Suppose we want to travel from San Francisco to Peking.
Top-down tells us that when we have to change planes in an
intermediate city, we will always be able to find the gate of
the outgoing plane, so we can eliminate the corresponding variables
from the problem.  Bottom-up may tell us that the main problem
is getting the Chinese visa, and the problem can be divided into
getting the visa and then using it.  In fact, the problem of getting
to Peking has a more complex structure.


.SKIP 2
.bb "#. Reduction of Problems to Finite State"

	The blocks problem can be axiomatized in first order logic
as follows:  We use the variable ⊗s to represent states of the
world, and ⊗move(x,y,s) to represent the new state of the world
that results from moving the block ⊗x onto the block ⊗y when the
world is in state ⊗s.  (In the "situation calculus" of (McCarthy
and Hayes 1970), ⊗s is a situation variable).  Statements about
one block being on top of another can be represented in two ways:
one leads to Boolean search problems and the other leads to
finite state search problems.  The first is to introduce a relation
⊗on(x,y,s) asserting that the block ⊗x is on the block ⊗y in
state ⊗s, and the second is to introduce a function ⊗support(x,s).  
These are related by

	∀%2x y s.(y = support(x,s) ≡ on(x,y,s)).%1

The axioms for moving are

	∀%2x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

⊃ on(x,y,move(x,y,s)) ∧ ∀z.(z≠y ⊃ ¬on(x,z,move(x,y,s))%1

∧ ∀w z.(w≠x ⊃ on(w,z,move(x,y,s)) ≡ on(w,z,s)))%1

using ⊗on, and

	∀%2x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

⊃ support(x,move(x,y,s)) = y ∧ ∀w.(w≠x ⊃ support(w,move(x,y,s)) = support(w,s))).%1

If we admit conditional expressions in our formalism for first order
logic, the second axiom simplifies slightly to

	∀%2x y s w.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

⊃ support(w,move(x,y,s)) = %3if%2 w=x %3then%2 y %3else%2 support(w,s)).%1

The expression ⊗clear(x,s) which appears above is defined by

	%2∀x s.(clear(x,s) ≡ ∀z.¬on(z,x.s))%1

or

	∀%2x s.(clear(x,s) ≡ ∀z.(support(z,s) ≠ x))%1.

	These axioms are correct for the ⊗quasi-static block moving
problem regardless of how many blocks there are.  To obtain a
Boolean search or finite-state search problem, a person or computer
program must make appropriate substitutions of a small finite number
of blocks into the axioms, settle on an initial state and final
condition and give a special role to the function ⊗move(x,y,s) and
to the variable ⊗s itself.

	Such a process is analogous to trying to prove first order
logic problems by making a finite set of substitutions from the
Herbrand universe into the axioms and then solving a problem in
propositional calculus.  The trick in either case is to find the
right set of substitutions.  Such methods for predicate calculus
were proposed by Martin Davis, and he experimented with a very
simple form, but they were superseded by the resolution methods
that don't make all the substitutions at once.

	In my opinion, the very fast algorithms that can be used
after the substitutions have been made (e.g. the TAUT algorithm
from FOL by Chandra and Weyhrauch) make it worthwhile to try to
find heuristics for making a good set of substitutions.


.bb "#. Hardware"

	The standard algorithms for Boolean and finite state search
can be implemented in parallel hardware and should run extremely
fast.  The idea is to have parallel simple processors generate points
in the search space and compute neighbors in parallel and generate
pointers to neighbors.  Then the distance from the initial point
can propagate through the space, and the solution path will be found
in a number of stpes proportional to the length of the shortest
path.  We envisage such parallel hardware as a satellite to a
conventional computer that would give it parts of the search space
to explore.  In the design, the top-down and bottom-up heuristics
must also be considered.

	Naturally, much more must be learned about the algorithms
for reducing problems to Boolean and finite-state searches, before
one could seriously contemplate building such hardware.

.skip 2
.bb "#. Limitations"

	So far as I know, there aren't any significant AI problems
that directly take a finitary form.  This is because almost all
intelligent behavior involves the application of general laws,
even if only the laws governing the effects of moving blocks,
to particular cases, and the finitary systems considered in this
paper come up only after the general laws have been instantiated.
Therefore, the utility of the method depends on finding ways to
instantiate the general laws before the search is made.

	Another way of seeing the limitations of finitary search
is to try to apply it to games.  Suppose there are only five
pieces left on a chess board.  Then we can use the locations
of the pieces as variables, so the position is characterized by
the values of five six-bit quantities.  So far so good since
that will fit into one 36-bit machine word.

	Another matter that works out well is the search algorithm
itself.  Instead of the simple tree search of the previous problems,
we will need an αα-β search, but this is helpful, because it reduces
the size of the space to be searched.  The general search algorithm
is different,
but the successors calculation is just the application of a set of
transformations.

	The first difficulty is the goal condition.  In case the
goal is checkmate, the number of possible goal states is very large,
and they are not summarized by giving values to a subset of the
variables.  However, if the goal were merely to promote a pawn,
the goal might be simply characterized.

	The real difficulty is that there would be too many
transformations.  There would be at least one for every pair
consisting of an initial square and destination square for each
piece, i.e. about 5 x 64 x 10 = 3200.  Actually there would be
several times that number, because the condition for moving a
piece from a given square to a given other square might require
several transformations.

	I can't quite convince myself that the formalism couldn't
be made to work for small chess endgames, but it certainly wouldn't
be very natural.
In fact, I believe it would work quite well for some ⊗go and
checker end games.   In ⊗go problems where all the moves take
place in a small region, the transformation rules may be reasonably
few, but the goal condition may be rather difficult to compute.

	To the extent that reduction to finitary search is useful,
it would satisfy some people's desire for a method in artificial
intelligence that doesn't come from natural intelligence, since
it depends explicitly on a computer's ability to manipulate bits
of information very rapidly once the meaning has been abstracted
from them.
.bb "Search of Cartesian product spaces."

	There is a small general theory of search.  It is discussed,
for example, in (Nilsson 19xx).  Its concepts include depth-first
and breadth first searches, and-or graphs, hill-climbing, and the
αα-β search method for game trees.  After this general theory,
we have to get down to particular cases.

	Suppose that the search space has a Cartesian product
structure, and most search spaces do.  The object of this
section is to discuss some search methods that take advantage
of some favorable conditions tha∨ may obtain, i.e. we will
try to find sufficient conditions for the applicability of
the methods.